1. Field of the Invention
The present invention relates to a multiplierless finite impulse response (FIR) digital filter and a method of designing the same, which can allow a hardware resource to be designed with a small structure when an FIR digital filter required by a transmitting or receiving terminal of a base band unit in a mobile telecommunication system is implemented in a communication system based on orthogonal frequency-division multiplexing (OFDM), orthogonal frequency-division multiple access (OFDMA) and code division multiple access (CDMA) which have recently been used as communication is improved in speed and increased in traffic.
2. Discussion of Related Art
In a typical mobile telecommunication system used with a base station and a mobile terminal, a digital filter filtering a base band digital signal is called a pulse shaping filter (PSF), and the PSF includes an infinite impulse response (IIR) filter that uses feedback for returning output to input, and a finite impulse response (FIR) filter that does not use the feedback. Hereinafter, the FIR filter will be used in describing the present invention.
In the digital filter, a bit of input data is multiplied by a coefficient in order to process a signal, so that a register is needed to temporarily store the data each processed by a bit unit. As a bit of input or the number of tap of coefficient representation becomes larger, a filtering property gets better but there are needed more registers and more logic circuits.
A high-speed linear-phase FIR filter, which has been widely used in the mobile telecommunication system, is generally designed to operate as a digital circuit using a complementary metal oxide semiconductor (CMOS). The design requirement of the FIR filter include a bit of the input data, the number of tap, and a bit of the coefficient representing the size of each tap. In proportion to the size of each given requirement, a hardware complication of the FIR filter is determined. Further, a hardware size of the FIR filter is determined and evaluated by the number of multipliers used for multiplying the input data by the coefficient of each tap rather than a bit of the general input data.
FIG. 1A illustrates a typical example of an FIR filter that is simply implemented by an arithmetic formula. As shown in FIG. 1A, an FIR filter 10 having a conventional multiplier 12 receives input data Di and shifts the input data Di per clock cycle using a shift register provided in the multiplier 12. The shifted data is multiplied by a given input coefficient Coef and summed up through an adder chain 14, thereby finally outputting a result.
Meanwhile, to solve the foregoing problems, there have been proposed various techniques and design methods using an adder/subtracter without the multiplier. As an representative example among these conventional arts, as shown in FIG. 1B, a method has been widely known, in which a given input coefficient Coef is converted into a canonic signed digit (CSD) and the input data is filtered through the adder/subtracter using the converted value. In this conventional method, a CSD code (1, 0, −1) of when a binary number b'1 is minimum is obtained and undergoes a process of finding the maximum common elements for a common subexpression elimination (CSE). Then, from the results, a shift/adder 24 and an adder chain 26 are used in performing an operation corresponding to multiplication, thereby realizing the filter.
In a conventional filter structure using an existing CSD, a binary multiplier operates depending on a shifter and an adder, so that it is important in designing the filter to find a method capable of reducing the number of times that adding operations are performed. Since the early 1990's, many researches into the CSD have been carried out. Further, various heuristic algorithms have been hitherto proposed according as a problem of finding an optimal minimum signed digit (MSD) format is estimated as an NP-complete. Nevertheless, in the filter using the existing CSD, when a given coefficient is represented into the CSD, it is known that the number of b'1 averages about ⅓ through ½, and there is a limit in that the shift/adder, i.e., an adding/subtracting operation substituting for the multiplication is needed as many as the number of b'1.